package com.ycyoes.test.hollis.algorithm;


import com.ycyoes.demos.geetime.algorithm.chapter5.Array;

import java.util.Arrays;

public class CommonAlgorithm {

    //冒泡排序
    //嵌套了两个for循环，所以冒泡的时间复杂度是O(n^2)，同时因为swap的时候用到了一个临时变量，所以空间复杂度是O(1)
    public static void popSort(int[] array) {
        for (int i = array.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (array[j] > array[j+1]) {
                    swap(array,j, j+1);
                }
            }
        }
    }

    //选择排序
//    遍历n次数组，每次“选择”最大或者最小的值，同时置换位置，直到遍历完成
    //和冒泡排序一样，选择排序的时间复杂度也是O(n^2)，空间复杂度是O(1)
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int min = Integer.MAX_VALUE;
            int index = -1;
            for(int j = i; j < array.length; j++) {
                if (array[j] < min) {
                    min = array[j];
                    index = j;
                }
            }
            swap(array, i, index);
        }
    }

    //每遍历一个元素，都把这个元素和之前遍历的元素作比较，如果该元素小于之前的元素，就把该元素“插入”到对应的位置。
    public static void insertSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int pos = array[i];
            int index = i;
            for(int j = i - 1; j >= 0; j--) {
                if (pos < array[j]) {
                    swap(array, index, j);
                    index = j;
                }
            }
        }
    }

    /**
     * 快排分为以下几步：
     * 1. 随机选取一个基准数 target
     * 2. 重新排序，把大于基准数的放到左边，小于基准数的放到右边
     * 3. 将左右两边的分区分片处理，处理逻辑和第一步相同
     * @param array
     * @param start
     * @param end
     */
    public static void quickSort(int[] array, int start, int end) {
        int i = start, j = end;
        int target = array[start];
        while (i < j) {
            //找到右侧小于target的值
            while (i < j && target <= array[j]) {
                j--;
            }
            // 找到左侧大于target的值
            while (i < j && array[i] <= target) {
                i++;
            }
            if (i < j) {
                swap(array, i, j);
            }
        }
        // 将基准位和中间的值交换
        swap(array, start, j);
        // 处理基准位左边的分片
        if (i - 1 > start){
            quickSort(array, start, i - 1);
        }
        // 处理基准位右边的分片
        if (j + 1 < end){
            quickSort(array,j + 1, end);
        }

    }


    public static void swap(int[] array, int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    public static void main(String[] args) {
        int[] a = {6,2,9,3,1,2};
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
//        popSort(a);
//        selectSort(a);
//        insertSort(a);
        quickSort(a, 0, a.length-1);
        System.out.println("-------------------");
        Arrays.stream(a).forEach(System.out::println);
//        for (int i = 0; i < a.length; i++) {
//            System.out.println(a[i]);
//        }
    }
}
